package example2;

import common.ListNode;
import utils.ListNodeUtil;

import java.util.HashSet;
import java.util.Set;

//142. 环形链表 II
public class LeetCode142 {
    public static void main(String[] args) {
        Integer[] arr = {-1,-7,7,-4,19,6,-9,-5,-2,-5};
        ListNode head = ListNodeUtil.transformArrayToListNode(arr);
        System.out.println(new Solution142_2().detectCycle(head).val);
    }
}

/**
 * 方法二：快慢指针         空间复杂度为  O(1)的算法
 * 1.证明有环的情况下快慢指针一定会相遇：
 *      快指针为 A ，慢指针为 B 。假设B进入环的起点时，A已经走到离起点 x 的距离。因为B走一圈A能走两圈，
 *      假设B走一圈之内A追不上，那么B会回到起点，A也会回到这个x的位置，但是既然A已经经过两圈到 x 了，那么
 *      说明A早都第二次经过起点了，此时A早就将B超过了，所以B走一圈之内一定会被A追上。假设A刚好在B后面一格，
 *      那么B走一格，A走两格，此时A、B刚好相遇。假设A在B后面2格，那么继续走一格之后A只在B后面一格，
 *      下一次注定相遇。    所以可以证明A一定会在B走一圈之内与B相遇。
 * 2.假设未成环的部分长 a，A和B在环中离环的起点长度为 b 的地方相遇，相遇点到起点距离为 c。
 *      因为通过证明B走一圈之内会与A相遇，A走过的距离为 a + n(b+c) + b，B走的距离为 a + b
 *      所以得出：a + n(b+c) + b = 2a + 2b => a = (n-1)(b+c) + c
 * 3.所以未成环的部分等于环周长的整数倍 加上 快慢指针相遇点继续前进到起点的距离。
 * 4.所以本体思路就是当快慢指针相遇时，此时再安排一个指针ptr从链表头节点开始一格一格走，当ptr和慢指针B相遇时，
 *   此时两者相遇点就是环的起点。
 */
class Solution142_2 {
    public ListNode detectCycle(ListNode head) {
        if(head == null)   return null;
        ListNode slow = head;
        ListNode fast = head;
        while(fast.next != null && fast.next.next != null){
            slow = slow.next;
            fast = fast.next.next;
            if(slow == fast){
                //此时再准备一个指针ptr
                ListNode ptr = head;
                while(true){
                    if(ptr == slow) return ptr;
                    ptr = ptr.next;
                    slow = slow.next;
                }
            }
        }
        return null;
    }
}

/**
 * 方法一：hash表存储已访问过的元素
 */
class Solution142_1 {
    public ListNode detectCycle(ListNode head) {
        if(head == null || head.next == null)   return null;
        Set<ListNode> set = new HashSet<>();
        set.add(head);
        set.add(head.next);
        ListNode now = head.next.next;
        while(now != null){
            if(set.contains(now)){
                return now;
            }else{
                set.add(now);
            }
            now = now.next;
        }
        return null;
    }
}
